{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Number of Moves to Seat Everyone"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minMovesToSeat"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #使每位学生都有座位的最少移动次数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>一个房间里有 <code>n</code>&nbsp;个座位和 <code>n</code>&nbsp;名学生，房间用一个数轴表示。给你一个长度为 <code>n</code>&nbsp;的数组&nbsp;<code>seats</code>&nbsp;，其中&nbsp;<code>seats[i]</code> 是第 <code>i</code>&nbsp;个座位的位置。同时给你一个长度为 <code>n</code>&nbsp;的数组&nbsp;<code>students</code>&nbsp;，其中&nbsp;<code>students[j]</code>&nbsp;是第 <code>j</code>&nbsp;位学生的位置。</p>\n",
    "\n",
    "<p>你可以执行以下操作任意次：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>增加或者减少第&nbsp;<code>i</code>&nbsp;位学生的位置，每次变化量为 <code>1</code>&nbsp;（也就是将第 <code>i</code>&nbsp;位学生从位置 <code>x</code>&nbsp;移动到 <code>x + 1</code>&nbsp;或者 <code>x - 1</code>）</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回使所有学生都有座位坐的 <strong>最少移动次数</strong>&nbsp;，并确保没有两位学生的座位相同。</p>\n",
    "\n",
    "<p>请注意，初始时有可能有多个座位或者多位学生在 <strong>同一</strong>&nbsp;位置。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>seats = [3,1,5], students = [2,7,4]\n",
    "<b>输出：</b>4\n",
    "<b>解释：</b>学生移动方式如下：\n",
    "- 第一位学生从位置 2 移动到位置 1 ，移动 1 次。\n",
    "- 第二位学生从位置 7 移动到位置 5 ，移动 2 次。\n",
    "- 第三位学生从位置 4 移动到位置 3 ，移动 1 次。\n",
    "总共 1 + 2 + 1 = 4 次移动。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>seats = [4,1,5,9], students = [1,3,2,6]\n",
    "<b>输出：</b>7\n",
    "<strong>解释：</strong>学生移动方式如下：\n",
    "- 第一位学生不移动。\n",
    "- 第二位学生从位置 3 移动到位置 4 ，移动 1 次。\n",
    "- 第三位学生从位置 2 移动到位置 5 ，移动 3 次。\n",
    "- 第四位学生从位置 6 移动到位置 9 ，移动 3 次。\n",
    "总共 0 + 1 + 3 + 3 = 7 次移动。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>seats = [2,2,6,6], students = [1,3,2,6]\n",
    "<b>输出：</b>4\n",
    "<b>解释：</b>学生移动方式如下：\n",
    "- 第一位学生从位置 1 移动到位置 2 ，移动 1 次。\n",
    "- 第二位学生从位置 3 移动到位置 6 ，移动 3 次。\n",
    "- 第三位学生不移动。\n",
    "- 第四位学生不移动。\n",
    "总共 1 + 3 + 0 + 0 = 4 次移动。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == seats.length == students.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;= seats[i], students[j] &lt;= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-number-of-moves-to-seat-everyone](https://leetcode.cn/problems/minimum-number-of-moves-to-seat-everyone/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-number-of-moves-to-seat-everyone](https://leetcode.cn/problems/minimum-number-of-moves-to-seat-everyone/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,1,5]\\n[2,7,4]', '[4,1,5,9]\\n[1,3,2,6]', '[2,2,6,6]\\n[1,3,2,6]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        seats.sort()\n",
    "        students.sort()\n",
    "        ans = 0\n",
    "        n = len(students)\n",
    "        for i in range(n):\n",
    "            ans += abs(students[i] - seats[i]) \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        seats.sort()\n",
    "        students.sort()\n",
    "        return int(sum ([math.fabs(students[i]-seats[i]) for i in range(len(seats))]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        seats.sort()\n",
    "        students.sort()\n",
    "        res = 0\n",
    "        for i in range(len(seats)):\n",
    "            res += abs(seats[i]-students[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        seats.sort()\n",
    "        students.sort()\n",
    "        res = 0\n",
    "        for i in range(len(seats)):\n",
    "            res += abs(seats[i] - students[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        return sum(abs(i - j) for i, j in zip(sorted(seats), sorted(students)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        seats = sorted(seats) \n",
    "        students = sorted(students) \n",
    "        result = 0\n",
    "        for i in range(len(seats)):\n",
    "            result += abs(seats[i] - students[i])  \n",
    "        return result\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        seats.sort()\n",
    "        students.sort()\n",
    "        ans = 0\n",
    "        for i in range(len(seats)):\n",
    "            ans += abs(seats[i] - students[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        return sum(abs(i-j) for i, j in zip(sorted(seats), sorted(students)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        seats.sort()\n",
    "        students.sort()\n",
    "        return sum([abs(i - j) for i, j in zip(seats, students)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        seats.sort()\n",
    "        students.sort()\n",
    "\n",
    "        return sum(abs(x-y)  for x,y in zip(seats,students))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        seats.sort()\n",
    "        students.sort()\n",
    "        ans = 0\n",
    "        for i in range(len(seats)):\n",
    "            ans += abs(students[i]-seats[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        seats.sort()\n",
    "        students.sort()\n",
    "        res = 0\n",
    "        for i in range(len(seats)):\n",
    "            res += abs(seats[i]-students[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        seats.sort()\n",
    "        students.sort()\n",
    "        s=list(zip(seats,students))\n",
    "        return sum(abs(i-j) for i,j in s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        seats.sort()\n",
    "        students.sort()\n",
    "        return sum(abs(x-y) for x, y in zip(seats, students))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        seats.sort()\n",
    "        students.sort()\n",
    "        n = len(seats)\n",
    "        return sum(abs(seats[i]-students[i]) for i in range(0,n))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        seats.sort()\n",
    "        students.sort()\n",
    "        ans = 0\n",
    "        for seat , student in zip(seats,students):\n",
    "            ans += abs(seat - student)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        seats.sort()\n",
    "        students.sort()\n",
    "        return sum(abs(x - y) for x, y in zip(seats, students))\n",
    "\n",
    "# 作者：力扣官方题解\n",
    "# 链接：https://leetcode.cn/problems/minimum-number-of-moves-to-seat-everyone/solutions/2037615/shi-mei-wei-xue-sheng-du-you-zuo-wei-de-oll4i/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        seats.sort()\n",
    "        students.sort()\n",
    "        return sum(abs(x-y) for x,y in zip(seats,students))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        seats.sort()\n",
    "        students.sort()\n",
    "        ans = 0\n",
    "        for i in range(len(seats)):\n",
    "            ans += abs(seats[i] - students[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        return sum(abs(i-j) for i, j in zip(sorted(seats), sorted(students)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        seats.sort()\n",
    "        students.sort()\n",
    "\n",
    "        summ = 0\n",
    "        for i in range(len(seats)):\n",
    "            summ += abs(seats[i]-students[i])\n",
    "        \n",
    "        return summ"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        seats.sort()\n",
    "        students.sort()\n",
    "        ans = 0\n",
    "        for i in range(len(seats)):\n",
    "            ans += abs(seats[i] - students[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        seats.sort()\n",
    "        students.sort()\n",
    "        Sum = 0\n",
    "        for x,y in zip(seats,students):\n",
    "            Sum += abs(x-y)\n",
    "\n",
    "        return Sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        seats.sort()\n",
    "        students.sort()\n",
    "        return sum(abs(x-y) for x, y in zip(seats, students))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        amount=0\n",
    "        n = len(seats)\n",
    "        seats.sort()\n",
    "        students.sort()\n",
    "        for i in range(n):\n",
    "            amount += abs(seats[i]-students[i])     \n",
    "        return amount\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        seats.sort()\n",
    "        students.sort()\n",
    "        return sum(abs(seats[i]-students[i]) for i in range(len(seats)) )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        seats.sort()\n",
    "        students.sort()\n",
    "        return sum(abs(x - y) for x, y in zip(seats, students))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        return sum(abs(i-j) for i, j in zip(sorted(seats), sorted(students)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        seats.sort()\n",
    "        students.sort()\n",
    "        cnt = 0\n",
    "        for i in range(len(seats)):\n",
    "            cnt += abs(seats[i] - students[i])\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        seats.sort()\n",
    "        students.sort()\n",
    "        return sum(abs(x-y) for x,y in zip(seats,students))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        seats.sort()\n",
    "        students.sort()\n",
    "        sum = 0\n",
    "        for i in range(len(seats)):\n",
    "            sum += abs(seats[i] - students[i])\n",
    "        return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        seats.sort()\n",
    "        students.sort()\n",
    "        return sum(abs(a-b) for a,b in zip(seats,students))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        seats.sort()\n",
    "        students.sort()\n",
    "        a=0\n",
    "        for i in range(len(seats)):\n",
    "            a+=abs(seats[i]-students[i])\n",
    "                \n",
    "        return a\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        seats.sort()\n",
    "        students.sort()\n",
    "        a=0\n",
    "        for i in range(len(seats)):\n",
    "            a+=abs(seats[i]-students[i])\n",
    "                \n",
    "        return a\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        if sorted(seats)==sorted(students):\n",
    "            return 0\n",
    "        seats=sorted(seats)\n",
    "        students=sorted(students)\n",
    "        cnt=0\n",
    "        for i,j in zip(seats,students):            \n",
    "                cnt += abs(i-j)\n",
    "                \n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        seats.sort()\n",
    "        students.sort()\n",
    "        return sum(abs(x - y) for x, y in zip(seats, students))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        seats.sort()\n",
    "        students.sort()\n",
    "\n",
    "        summ = 0\n",
    "        for i in range(len(seats)):\n",
    "            summ += abs(seats[i]-students[i])\n",
    "        \n",
    "        return summ"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        seats.sort()\n",
    "        students.sort()\n",
    "        return sum(abs(a-b) for a, b in zip(seats, students))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        seats.sort()\n",
    "        students.sort()\n",
    "        sum = 0\n",
    "        for i in range(len(seats)):\n",
    "            sum += abs(seats[i] - students[i])\n",
    "        return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        a=sorted(seats)\n",
    "        b=sorted(students)\n",
    "        c=0\n",
    "        for i in range(0,len(seats)):\n",
    "            c+=abs(int(a[i])-int(b[i]))\n",
    "        return c\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        seats.sort()\n",
    "        students.sort()\n",
    "        return sum(abs(x - y) for x, y in zip(seats, students))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        seats.sort()\n",
    "        students.sort()\n",
    "        res=0\n",
    "        for x,y in zip(seats,students):\n",
    "            res +=x-y if x>y else y-x\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        seats.sort()\n",
    "        students.sort()\n",
    "        moveTimes = 0\n",
    "        for i in range(len(seats)) :\n",
    "            moveTimes += abs(seats[i] - students[i])\n",
    "\n",
    "        return moveTimes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        seats.sort()\n",
    "        students.sort()\n",
    "        sum = 0\n",
    "        for i in range(len(seats)):\n",
    "            sum += abs(seats[i] - students[i])\n",
    "        return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        return sum(abs(a - b ) for a, b in zip(sorted(seats), sorted(students)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        seats.sort()\n",
    "        students.sort()\n",
    "        return sum(abs(x - y) for x, y in zip(seats, students))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        seats.sort()\n",
    "        students.sort()\n",
    "        return sum(abs(x-y) for x,y in zip(seats,students))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        return sum(abs(x - y) for x, y in zip(sorted(seats), sorted(students)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        seats.sort()\n",
    "        students.sort()\n",
    "        count=0\n",
    "        for i in range(len(seats)):\n",
    "            count+=abs(seats[i]-students[i])\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        heapq.heapify(seats)\n",
    "        heapq.heapify(students)\n",
    "        sum=0\n",
    "        while len(seats)>=1:\n",
    "            sum+=abs(heapq.heappop(seats)-heapq.heappop(students))\n",
    "        return sum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        seats.sort()\n",
    "        students.sort()\n",
    "        return sum(abs(a - b) for a, b in zip(seats, students))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        seats.sort()\n",
    "        students.sort()\n",
    "        cnt=0\n",
    "        for i in range(len(seats)):\n",
    "            cnt+=abs(seats[i]-students[i])\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        seats.sort()\n",
    "        students.sort()\n",
    "        return sum(abs(x - y) for x, y in zip(seats, students))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        cnt = 0\n",
    "        seats.sort()\n",
    "        students.sort()\n",
    "        for i, j in zip(seats, students):\n",
    "            cnt += abs(i-j)\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        seats = sorted(seats)\n",
    "        students = sorted(students)\n",
    "        return sum(abs(s - t) for s, t in zip(seats, students))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        seats.sort()\n",
    "        students.sort()\n",
    "        res=0\n",
    "        for i in range(len(seats)):\n",
    "            res+=abs(students[i]-seats[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        res = 0\n",
    "        seats.sort()\n",
    "        students.sort()\n",
    "        for i in range(0,len(seats)):\n",
    "            res += abs(seats[i] - students[i])\n",
    "        return res\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        seats.sort()\n",
    "        students.sort()\n",
    "        return sum(abs(seat - student) for seat, student in zip(seats, students))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        seats.sort()\n",
    "        students.sort()\n",
    "        return sum(abs(x - y) for x, y in zip(seats, students))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        seats.sort()\n",
    "        students.sort()\n",
    "        return sum(abs(x - y) for x, y in zip(seats, students))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        seats.sort()\n",
    "        students.sort()\n",
    "        sum = 0\n",
    "        for i in range(len(seats)):\n",
    "            sum += abs(seats[i] - students[i])\n",
    "        return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        # 题意：让两个数组完全相等的最少操作数，students中的数每次只能加1或者减1\n",
    "\n",
    "        # 思路1：两数组排序，对应索引元素相减的绝对值累加起来就是结果\n",
    "\n",
    "        seats.sort()\n",
    "        students.sort()\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(len(seats)):\n",
    "            ans += abs(seats[i]-students[i])\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def gb_sort(lists):\n",
    "    if len(lists) <= 1:\n",
    "        return lists\n",
    "    vul = len(lists) // 2\n",
    "    left = gb_sort(lists[vul:])\n",
    "    right = gb_sort(lists[:vul])\n",
    "    return gb_1_sort(left, right)\n",
    "\n",
    "\n",
    "def gb_1_sort(left, right):\n",
    "    l, r = 0, 0\n",
    "    res = []\n",
    "    while l < len(left) and r < len(right):\n",
    "        if left[l] < right[r]:\n",
    "            res.append(left[l])\n",
    "            l += 1\n",
    "        else:\n",
    "            res.append(right[r])\n",
    "            r += 1\n",
    "    res += list(left[l:])\n",
    "    res += list(right[r:])\n",
    "    return res\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        b = []\n",
    "        c = []\n",
    "        b = gb_sort(seats)\n",
    "        c = gb_sort(students)\n",
    "        a = 0\n",
    "        for i in range(len(b)):\n",
    "            a += abs(b[i] - c[i])\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        seats=sorted(seats)\n",
    "        students=sorted(students)\n",
    "        t = 0\n",
    "        for i in range(len(seats)):\n",
    "            if seats[i]>students[i]:\n",
    "                t = t+seats[i]-students[i]\n",
    "            else:\n",
    "                t = t+students[i]-seats[i]\n",
    "        return t\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        return sum(abs(i-j) for i, j in zip(sorted(seats), sorted(students)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "\n",
    "\n",
    "\n",
    "        seats.sort()\n",
    "        students.sort()\n",
    "        fin=0\n",
    "        for i in range(len(seats)):\n",
    "            fin+= abs(seats[i]-students[i])\n",
    "        return fin\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        seats.sort()\n",
    "        students.sort()\n",
    "        return sum(abs(a-b) for a,b in zip(seats,students))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        seats.sort()\n",
    "        students.sort()\n",
    "        n = len(seats)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans += abs(seats[i] - students[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        return sum(abs(x - y) for x, y in zip(sorted(seats), sorted(students)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        self.quick_sort(0,len(seats)-1,seats)\n",
    "        self.quick_sort(0,len(students)-1,students)\n",
    "        s=0\n",
    "        for i in range(len(students)):\n",
    "            d=seats[i]-students[i]\n",
    "            s+=d if d>0 else -d\n",
    "        return s \n",
    "\n",
    "    def quick_sort(self,left,right,arr):\n",
    "        if left>=right:\n",
    "            return\n",
    "            \n",
    "        p=arr[left]\n",
    "        flag=0\n",
    "        i=left\n",
    "        j=right\n",
    "        while i!=j:\n",
    "            if flag==0:\n",
    "                if p>arr[j]:\n",
    "                    arr[i]=arr[j]\n",
    "                    i+=1\n",
    "                    flag=1\n",
    "                else:\n",
    "                    j-=1\n",
    "            else:\n",
    "                if p<arr[i]:\n",
    "                    arr[j]=arr[i]\n",
    "                    j-=1\n",
    "                    flag=0\n",
    "                else:\n",
    "                    i+=1\n",
    "        arr[i]=p\n",
    "        self.quick_sort(left,i,arr)\n",
    "        self.quick_sort(i+1,right,arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        res=0\n",
    "        seats.sort()\n",
    "        students.sort()\n",
    "        for x,y in zip(seats,students):\n",
    "            res+=abs(x-y)\n",
    "            print(x,y)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        return sum(abs(a-b) for a,b in zip(sorted(seats),sorted(students)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:\n",
    "        counter = 0\n",
    "        seat_sorted = sorted(seats)\n",
    "        students_sorted = sorted(students)\n",
    "        print(seat_sorted, students_sorted)\n",
    "        for i in range(len(seats)):\n",
    "            counter += abs(seat_sorted[i] - students_sorted[i])\n",
    "        return counter"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
